def sift(li, low, high):
    i = low  # 记录父节点位置
    j = 2 * i + 1  # 记录左孩子节点位置
    tmp = li[low]  # 记录父节点的值

    # 循环找到合适的位置
    while j <= high:
        if j + 1 <= high and li[j] < li[j + 1]:
            j = j + 1
        if li[j] > tmp:
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:
            li[i] = tmp
            break
    else:
        li[i] = tmp


def heap_sort(li):
    n = len(li)
    # 建堆
    for i in range((n - 2) // 2, -1, -1):
        # i是指最后一个叶子节点
        sift(li, i, n - 1)
    print(li)
    # 排序
    for i in range(n - 1, -1, -1):
        li[0], li[i] = li[i], li[0]
        sift(li, 0, i - 1)


li = [2, 8, 5, 0, 1, 6, 4, 3, 10, 4, 9,]
heap_sort(li)
print(li)
